for your own convenience so that you can revisit the lecture later.

Okay, again, what we're going to do today is I'll talk you through a pretty cool idea

which is hashing.

Hashing is in general a nice approach to map some values to some other values.

In our particular context, we use this to implement on average well performing dictionaries.

And then after that, we'll see how long we need, we don't need the entire slot this time.

That depends also a little bit on how much you want to discuss.

I know the weather is not so great today, so great that so many still attend today.

After that, I'll recap a little bit what we did.

Talk you a little bit through the syllabus, a little bit about exam, what things are expected,

how we do things usually, all it is from the last years which we expect to fade over the next couple

iterations of this course.

And then some logistics things and then we are done with the lecture part and we can complete this term.

Now, any early questions?

Otherwise, I'll just dig in and we'll directly go into hash maps.

Hash maps, in my opinion, is a little bit of an addition to the algorithms we have explored so far.

So you can use these sort of techniques for most of the data structures we have explored,

most useful for maps or dictionaries where we need a good access on average.

Right. We haven't really discussed how to implement a dictionary, right.

You know, the data structure in Python, which is just a dict.

You remember how the dict works.

You provide a key and a value and this is then added somehow magically to your dictionary.

And when you look it up, you can look it up like an index just with the key.

The key can be anything.

It can be a string, it can be an integer, it can be whatever.

You just look it up with the key and you get the value back.

You can replace things, you can put things into key value, you can add new things.

It's a very amazing data structure and you can do amazing things with it.

Like I showed you with the, if you remember the Fibonacci numbers,

you can compute more efficiently through dynamic programming by using a dictionary

where you store intermediate results and just look them up.

Now that look up needs to be efficient to make so that this works actually in practice.

And hashing is a way to make things more efficient than just O of N.

Because as you know, if you store a number of values,

if you want to find a certain value, you have to search all of these values, right?

Linear search, you can't be faster, O of N.

In the worst case, in the worst case.

Now we're starting to more and more look into sort of practical average cases.

The worst case is very often very unlikely.

If you have very large data, if you do smart things to your data,

the smarter you are, the less likely your worst case is.

And even if the worst case occurs, the worst case still needs to be manageable, right?

So it needs to be within the constraints of your computer memory,

so that you can't go beyond this.

And processing your entire computer's memory must be doable in finite time.

And as we know that is possible, it will take quite a while with modern computers,

but in theory you could do this in finite time.

Now, again, some more things we're discussing now.

So dictionaries, so in general terms, dictionaries are called maps in computer science.

Map is something where you have a key and get some value back.